CF39A C*++ Calculations

题意简述

给你一个含变量xx的式子,所有xx的系数为常数,定义模糊的部分按任意次序计算。如:a+++++aa+++++a既可以先算 a++a++ , 也可以先算++a++a

给你aa的初值,求算式的最大值。

样例:为了方便描述,用括号隔开

a=1                (5a++)(3++a)+(a++)a = 1~~~~~~~~~~~~~~~~ (5*a++)-(3*++a)+(a++)

计算顺序为:2,3,12,3,1

答案为:(53)(32)+(2)=11(5*3)-(3*2)+(2) = 11

进入正题

这道题可以贪心解决,我们不难想到,系数越小,我们越先算(减法系数取负)。
下面给出证明:

结论1:当系数相同时,a++a++++a++a的顺序对答案无影响。

证明:若原式有这样一个部分:(ka++) + (k++a)( k*a++)~+~ (k * ++a)

先算前部分:ka+k(a+2)k*a+k*(a+2)

先算后部分:k(a+1)+k(a+1)k*(a+1)+k*(a+1)

结果是相等的,同时,aa改变后的值也相等,证毕。

结论2:当系数不同时,系数小的先算

证明:考虑4个式子:(p = qp~\not=~q

(p++a)+(qa++)(p*++a)+(q*a++)

(p++a)+(q++a)(p*++a)+(q*++a)

(pa++)+(qa++)(p*a++)+(q*a++)

(pa++)+(q++a)(p*a++)+(q*++a)

先讨论第一个式子,其余同理。

先算左式:p(a+1)+q(a+1)p*(a+1)+q*(a+1)

先算右式:p(a+2)+qap*(a+2)+q*a

两式作差:qpq-p

q>pq>pqp>0q-p>0,即先算左式更优,刚好是小系数。

q<pq<p同理。


知道贪心策略后,代码实现不难,模拟求出系数与式子是++a++a还是a++a++
最后排序算出答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long

int a,len;
int k , f;
struct node{
	int a_i , fr;
	operator < ( const node &x ) {
		return a_i < x.a_i;
	}
}c[ 100005 ];
char s[ 1000005 ];
signed main( ) {
    scanf("%lld\n",&a);scanf("%s",s);
    int len = strlen( s );
    for( int i = 0 ; i < len ; i ++ ) {
        f = 1;
        if( s[ i ] == '-' ) f = -1 , i ++;
        if( s[ i ] == '+' && ( s[ i + 1 ] != '+' || ( s[ i + 1 ] == '+' && s[ i + 2 ] == '+' ) ) ) i ++;
        if( '0' <= s[ i ] && s[ i ] <= '9' ) {
            k ++;
            while( '0' <= s[ i ] && s[ i ] <= '9' ) {
                c[ k ].a_i = c[ k ].a_i * 10 + s[ i ] - '0';
                i ++;
            }
            i ++; c[ k ].a_i *= f;
            if( s[ i ] == '+' ) c[ k ].fr = 1;
            i += 2;
        }
        else if( s[ i ] == '+' ) {
            c[ ++ k ].a_i = f;
            c[ k ].fr = 1;
            i += 2;
        }
        else if( s[ i ] == 'a' ) {
            c[ ++ k ].a_i = f;
            i += 2;
        }
    }
    /*for( int i = 1 ; i <= k ; i ++ )
    	printf("%lld %lld\n",c[ i ].a_i,c[ i ].fr);*/
    sort( c + 1 , c + k + 1 );
    int Ans = 0;
    for( int i = 1 ; i <= k ; i ++ ) {
        Ans = Ans + c[ i ].a_i * ( c[ i ].fr ? a + 1 : a );
        a ++;
    }
    printf("%lld",Ans);
    return 0;
}